<!--
 * @Author: your name
 * @Date: 2021-07-27 17:59:18
 * @LastEditTime: 2021-08-11 15:13:31
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>排序算法的实现</title>
</head>

<body>
  <script>
    // 创建列表类
    function ArrayList() {
      this.array = []

      ArrayList.prototype.insert = function (item) {
        this.array.push(item)
      }

      ArrayList.prototype.toString = function () {
        return this.array.join('-')
      }

      // 交换两个位置的数据
      ArrayList.prototype.swap = function (m, n) {
        var temp = this.array[m]
        this.array[m] = this.array[n]
        this.array[n] = temp
      }

      // 冒泡排序
      ArrayList.prototype.bubbleSort = function () {
        // 1. 获取数组长度
        var length = this.array.length

        // 第一次：j = length -1，比较到倒数第一个位置
        // 第二次：j = length -2，比较到倒数第二个位置
        // ...
        for (var j = length - 1; j >= 0; j--) {
          // 第一次进来：i = 0，比较 0 和 1位置的两个数据，如果0位置大于1位置的数据
          // 最后一次进来：i = length -2，比较length - 1 和 length - 1 的两个数据
          for (var i = 0; i < j; i++) {
            if (this.array[i] > this.array[i + 1]) {
              // 交换两个数据
              this.swap(i, i + 1)
            }
          }
        }

      }

      // 选择排序
      ArrayList.prototype.selectionSort = function () {
        // 1. 获取数组的长度
        var length = this.array.length

        // 2. 外层循环：从0位置开始取数据
        for (var j = 0; j < length - 1; j++) {
          // 内存循环：从i+1位置开始和后面的数据进行比较
          var min = j
          for (var i = min + 1; i < length; i++) {
            if (this.array[min] > this.array[i]) {
              min = i
            }
          }
          this.swap(min, j)
        }

      }

      // 插入排序
      ArrayList.prototype.insertionSort = function () {
        // 1. 获取数组的长度
        var length = this.array.length

        // 2. 外层循环：从第一个位置开始获取数据，向前面局部有序进行插入
        for (var i = 0; i < length; i++) {
          // 3. 内层循环：获取i位置的元素，和前面的数据依次进行比较
          var temp = this.array[i]
          var j = i
          while (this.array[j - 1] > temp && j > 0) {
            this.array[j] = this.array[j - 1]
            j--
          }

          // 4. 将j位置的数据，放置temp
          this.array[j] = temp
        }
      }

      // 希尔排序
      ArrayList.prototype.shellSort = function () {
        // 1. 获取数组的长度
        var length = this.array.length

        // 2. 初始化的增量(间隔)
        var gap = Math.floor(length / 2)

        // 3. while循环(gap不断的缩小)
        while (gap >= 1) {
          // 4. 以gap作为间隔进行分组，对分组进行插入排序
          for (var i = gap; i < length; i++) {
            var temp = this.array[i]
            var j = i
            while (this.array[j - gap] > temp && j > gap - 1) {
              this.array[j] = this.array[j - gap]
              j -= gap
            }

            // 5. 将j位置的元素赋值temp
            this.array[j] = temp
          }

          // 6. 增量变化 / 2
          gap = Math.floor(gap / 2)
        }
      }

      // 快速排序
      /**
       * 1. 选择枢纽
       * a. 去出中位数、最右侧元素、最左侧元素，对三个数排序
       * b. 中位数换到倒数第二位
       */
      ArrayList.prototype.median = function (left, right) {
        // 1. 取出中间的位置
        var center = Math.floor((left + right) / 2)

        // 2. 判断大小，并且进行交换 然三个元素有序(对左侧、中位数、右侧 排序)
        if (this.array[left] > this.array[center]) {
          this.swap(left, center)
        }
        if (this.array[center] > this.array[right]) {
          this.swap(center, right)
        }
        if (this.array[left] > this.array[center]) {
          this.swap(left, center)
        }

        // 3. 将center换到right -1 位置
        this.swap(center, right - 1)
        return this.array[right - 1]
      }

      // 2. 快速排序实现
      ArrayList.prototype.quickSort = function () {
        this.quick(0, this.array.length - 1)
      }

      ArrayList.prototype.quick = function (left, right) {
        // 1. 结束条件
        if (left >= right) return

        // 2. 获取枢纽
        var pivot = this.median(left, right)

        // 3. 定义变量，用于记录当前找到的位置
        var l = left
        var r = right - 1

        // 4. 开始进行循环交换
        while (l < r) {
          // 左侧指针指向后一个元素
          while (this.array[l] < pivot) {
            ++l
          }
          // 右侧指针指向前一个元素
          while (this.array[r] > pivot) {
            --r
          }

          if (l < r) {
            this.swap(r, l)
          } else {
            break
          }
        }
        // 6. 将枢纽放置在正确的位置，i的位置
        this.swap(l, right - 1)

        // 7. 分而治之
        this.quick(left, l - 1)
        this.quick(l + 1, right)

      }

    }

    var list = new ArrayList()
    list.insert(66)
    list.insert(88)
    list.insert(12)
    list.insert(87)
    list.insert(100)
    list.insert(5)
    list.insert(566)
    list.insert(23)
    // 66,88,12,87,100,5,566,23
    list.quickSort()
    alert(list)
  </script>
</body>

</html>